Location-relevant services and applications have been widely-studied topics in the mobile computing community over the past few years. Most of the researchers focus on localization of devices/users. Currently, with the help of space satellites, meter-level positioning accuracy can be achieved in outdoor environments (e.g., using GPS, GLONASS, etc.), and at the same time, numerous approaches have also been proposed to localize users in indoor environments. Accurate localization techniques and map information make real-time navigation a reality. Most research efforts in navigation have been invested in path planning and optimization with given starting and destination locations. However, due to the lack of accurate map information, satisfactory navigation cannot always be achieved, especially in the last portion of a trip. For example, Google Map can navigate users to a building (more specifically, to the entrance of the building) from a place tens of miles away, but fails to find a feasible path to the final destination, the meeting room inside the building. We call this imperfection the last-mile navigation problem. The last mile was originally used in the field of communications to refer to the final leg of communications connectivity to retail customers. The last mile is typically the speed bottleneck in communication networks. Here the term ‘last mile’ refers to the imperfection in a navigation system.
The main reason for this problem is the map's insufficient path information, making the exact destination unknown and unreachable. Technically, most navigation services are only able to navigate a user to a place that is connected by at least one indexed path, such as a trunk road. If the end position is isolated in the map database (even if it is accessible in real life), navigation systems cannot connect coordinates of two positions. This type of navigation is sufficient during most part of a trip, but may fail to function properly in its “last mile.” For instance, Google Map cannot provide fine-grained navigation service in a public park or a large parking lot, let alone offer guidance to numerous points of interest inside a building.
The navigation problem is more complicated in indoor environments. Despite the existence of extensive research on indoor localization, few large-scale systems have been deployed due to the required labor-intensive and time consuming bootstrap effort (i.e., indoor map construction). Even with their deployment, indoor localization systems still face an onerous calibration process (e.g., for radio-based fingerprint systems) and need to deploy path planning algorithms to enable navigation.
To meet the ever-growing demand for navigation service and bridge the gap between the user's final destination and the end position provided by current navigation services (e.g., Google Map), this disclosure proposes a new lightweight, plug-and-play last-mile navigation system, referred to herein as FollowUp. The main idea of last-mile navigation system is to use “scent” or “crumbs” left behind by previous travelers (a.k.a., leaders). Specifically, during a trace-collection phase, the navigation system records a bunch of sensory data with a smartphone during the leader's walking trip. It then recognizes the leader's walking pattern (e.g., steps, turns, upstairs) and packs them together with information extracted from the geomagnetic field to build a reference trace. During a navigation phase, the navigation system installed in a follower's smartphone will compare current sensor readings with the reference trace, and navigates him, in real time, from the same starting point to the final destination. This way, irrespective of incomplete map information, the last-mile navigation system is able to navigate the followers to any Point of Interest (PoI) as long as it was visited before by a leader. For example, the meeting coordinator can provide attendees with data trace from the entrance of a building to the meeting venue to save time. Vendors and restaurant owners can collect data traces on their own from several entrances of a shopping center to their shops, and then share them with others for promotional purposes. In fact, the leader and the follower can be the same person. For example, one can record a trace from a parking spot to the airport terminal, and use it for reverse navigation back to his car after a multi-day trip.
Unlike other leader-follower navigation systems, the proposed system neither relies on an infrastructure (e.g., maps, WiFi APs, etc.) nor requires any additional hardware (e.g., beacons or landmarks). In addition, the proposed navigation system is an all-weather navigation system as it exploits people's natural walking pattern and the ubiquitous geomagnetic field, minimizing the constraints imposed on users.
This section provides background information related to the present disclosure which is not necessarily prior art.